Optimisation convexe : Au-delà de la convexité élémentaire : Conservation par supremum ponctuel

Alors que la convexité élémentaire couvre les sommes et les changements d'échelle, la conservation de la convexité par le supremum ponctuel est une opération fondamentale pour construire des fonctions convexes non triviales et établir la dualité. Elle affirme que même si nous avons une famille infinie non dénombrable de fonctions convexes, leur « enveloppe supérieure » reste convexe. Ce pont nous permet d'analyser des formes convexes complexes à l'aide de composants linéaires simples.

1. La Définition Technique

Pour une famille de fonctions $\{f(\cdot, y) \mid y \in \mathcal{A}\}$, le supremum ponctuel est défini comme :

$$g(x) = \sup_{y \in \mathcal{A}} f(x, y)$$

Le domaine de cette fonction est l'ensemble des points où toutes les fonctions de la famille sont définies et où le supremum est fini :

$$\text{dom } g = \{x \mid (x, y) \in \text{dom } f \text{ pour tout } y \in \mathcal{A}, \sup_{y \in \mathcal{A}} f(x, y) < \infty\}$$

L'Approche par l'Épigraphe

Géométriquement, l'épigraphe de la fonction du supremum est l'intersection des épigraphes individuels :

$$\text{epi } g = \bigcap_{y \in \mathcal{A}} \text{epi } f(\cdot, y)$$

Puisque chaque épigraphe individuel est un ensemble convexe (en raison de la convexité de $f(x, y)$ en $x$), et que l'intersection de tout nombre d'ensembles convexes est elle-même convexe, la convexité de $g(x)$ est garantie.

2. Exemples Importants

Fonction de support : $S_C(y) = \sup \{ y^T x \mid x \in C \}$. Cette fonction est toujours convexe, quels que soient les ensembles $C$ convexes ou non, car elle est le supremum de fonctions linéaires (affines) de $y$.
Distance au point le plus éloigné : $f(x) = \sup_{y \in C} \|x - y\|$. Même pour un ensemble $C$ irrégulier, $f(x)$ est convexe en $x$ car la norme est une fonction convexe de $x$.
Valeur propre maximale : Pour une matrice symétrique $X$, $f(X) = \lambda_{\max}(X)$ est convexe. Cela découle du quotient de Rayleigh : $\lambda_{\max}(X) = \sup\{y^T X y \mid \|y\|_2 = 1\}$. Il s'agit du supremum de fonctions linéaires de $X$.

Théorème : Représentation par des Fonctions Affines

Théorème

Presque toute fonction convexe peut être exprimée comme le supremum ponctuel d'une famille de fonctions affines (des sous-estimateurs globaux).

Intuition

En tout point $x_0$, une fonction convexe $f$ possède un hyperplan tangent (une fonction affine $h(x) = f(x_0) + g^T(x-x_0)$). En prenant le supremum de tous ces hyperplans tangents, nous reconstruisons exactement la fonction $f$.

🎯 Principe Fondamental

Le supremum ponctuel préserve la convexité et l'infimum ponctuel préserve la concavité. C'est ce qui explique la convexité des normes, des fonctions spectrales et des problèmes duaux.

$$g(x) = \sup_{y \in \mathcal{A}} f(x, y) \implies g \text{ est convexe si } f(\cdot, y) \text{ est convexe } \forall y$$

QUESTION 1

Si $f_1(x), f_2(x), \dots, f_n(x)$ sont des fonctions convexes, que pouvons-nous dire de $g(x) = \max\{f_1(x), \dots, f_n(x)\}$ ?

$g(x)$ est toujours convexe.

$g(x)$ est convexe uniquement si toutes les $f_i$ sont linéaires.

$g(x)$ est concave.

$g(x)$ est seulement quasi-convexe.

QUESTION 2

La fonction de support $S_C(y) = \sup_{x \in C} y^T x$ est convexe en $y$, même si $C$ est un ensemble non convexe. Pourquoi ?

Parce que $y^T x$ est linéaire (et donc convexe) en $y$ pour tout $x$ fixé.

Parce que l'ensemble $C$ est automatiquement traité comme son enveloppe convexe.

Parce que le produit scalaire est toujours une fonction positive.

Les fonctions de support sont convexes uniquement si $C$ est borné.

QUESTION 3

Quelle est la relation entre l'épigraphe de $g(x) = \sup f_i(x)$ et les épigraphes individuels $\text{epi } f_i$ ?

$\text{epi } g = \bigcap \text{epi } f_i$

$\text{epi } g = \bigcup \text{epi } f_i$

$\text{epi } g = \text{conv}(\bigcup \text{epi } f_i)$

Il n'y a pas de relation directe.

QUESTION 4

La norme spectrale d'une matrice $\|X\|_2 = \sigma_{\max}(X)$ est convexe parce que ...

Elle est le supremum des fonctions convexes $\|Xv\|_2$ sur les vecteurs unitaires $v$.

La somme des valeurs singulières est toujours convexe.

Toutes les normes sont des fonctions linéaires.

Les fonctions matricielles sont toujours convexes sur le cône semi-défini positif.

QUESTION 5

Si nous prenons l'infimum ponctuel d'une famille de fonctions concaves, quel est le résultat ?

Une fonction concave.

Une fonction convexe.

Une fonction linéaire.

Cela dépend du domaine.

Défi : Dualité et fonctions conjuguées

MATH008 Analyse Avancée

En analyse convexe, la fonction conjuguée $f^*$ est définie via le supremum ponctuel de fonctions affines : $f^*(y) = \sup_x (y^T x - f(x))$. Cette transformation est essentielle pour les problèmes d'optimisation duaux.

[Réponse brève] Condition d'ordre deux pour la convexité. Démontrer qu'une fonction $f$ deux fois différentiable est convexe si et seulement si son domaine est convexe et que $\nabla^2 f(x) \succeq 0$ pour tout $x \in \mathbf{dom} f.

Solution : En restreignant $f$ à une ligne arbitraire $g(t) = f(x + tv)$, la convexité de $f$ est équivalente à $g''(t) \geq 0$ pour tout $v$ et tout $t$ tel que $x+tv \in \text{dom } f$. Puisque $g'(t) = \nabla f(x + tv)^T v$ et $g''(t) = v^T \nabla^2 f(x + tv) v$, la condition $g''(t) \geq 0$ pour tout $v$ est équivalente à la matrice hessienne étant semi-définie positive : $\nabla^2 f(x) \succeq 0$.

[Réponse brève] Gradient et hessien de la fonction conjuguée. Supposons que $\bar{y}$ et $\bar{x}$ sont liés par $\bar{y} = \nabla f(\bar{x})$, et que $\nabla^2 f(\bar{x}) \succ 0$. (a) Montrer que $\nabla f^*(\bar{y}) = \bar{x}$. (b) Montrer que $\nabla^2 f^*(\bar{y}) = \nabla^2 f(\bar{x})^{-1}$. (Sortie requise : 250 mots)

Réponse de référence de l'enseignant : Pour traiter la partie (a), rappelons la définition de la fonction conjuguée $f^*(y) = \sup_x (y^T x - f(x))$. Pour une valeur fixe $y = \bar{y}$, si $f$ est différentiable et convexe, le supremum est atteint au point où le gradient de l'objectif $h(x) = \bar{y}^T x - f(x)$ s'annule. En posant $\nabla_x (\bar{y}^T x - f(x)) = 0$, on obtient $\bar{y} = \nabla f(x)$. Étant donné que le problème indique $\bar{y} = \nabla f(\bar{x})$, il s'ensuit que $\bar{x}$ est le maximiseur. Par la propriété de la fonction conjuguée au point d'optimalité, nous avons $f^*(\bar{y}) = \bar{y}^T \bar{x} - f(\bar{x})$. En dérivant des deux côtés par rapport à $\bar{y}$ et en appliquant le théorème de l'enveloppe (ou le fait que $\bar{x}$ est l'optimal), nous obtenons $\nabla f^*(\bar{y}) = \bar{x}$. Cela confirme que le gradient de la fonction conjuguée agit comme une application inverse du gradient de la fonction originale.

Pour la partie (b), nous dérivons la relation $\nabla f^*(\nabla f(x)) = x$ par rapport à $x$ en utilisant la règle de chaîne. Cela donne $\nabla^2 f^*(\nabla f(x)) \cdot \nabla^2 f(x) = I$, où $I$ est la matrice identité. En substituant $\bar{y} = \nabla f(\bar{x})$, nous obtenons $\nabla^2 f^*(\bar{y}) \cdot \nabla^2 f(\bar{x}) = I$. Étant donné que $\nabla^2 f(\bar{x}) \succ 0$, la hessienne est inversible. Ainsi, $\nabla^2 f^*(\bar{y}) = [\nabla^2 f(\bar{x})]^{-1}. Ce résultat élégant montre que la courbure locale de la fonction conjuguée est l'inverse (ou la matrice inverse) de la courbure de la fonction originale aux points correspondants. Cette relation est centrale à l'analyse des méthodes de type Newton dans l'espace dual et à la compréhension des transformations de Legendre en physique et en optimisation.